package alo.p3.work;

import java.util.HashMap;
//克隆链表（数据、next、random）
public class Clone {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    //使用散列表hashmap
    class Solution {
        public Node copyRandomList(Node head) {
            if(head==null) {
                return null;
            }
            //创建一个哈希表，key是原节点，value是新节点
            HashMap<Node,Node> map = new HashMap<Node,Node>();
            Node p = head;
            //将原节点和新节点放入哈希表中
            while(p!=null) {
                Node newNode = new Node(p.val);
                map.put(p,newNode);
                p = p.next;
            }
            p = head;
            //遍历原链表，设置新节点的next和random
            while(p!=null) {
                Node newNode = map.get(p);
                //p是原节点，map.get(p)是对应的新节点，p.next是原节点的下一个
                //map.get(p.next)是原节点下一个对应的新节点
                if(p.next!=null) {
                    newNode.next = map.get(p.next);
                }
                //p.random是原节点随机指向
                //map.get(p.random)是原节点随机指向  对应的新节点
                if(p.random!=null) {
                    newNode.random = map.get(p.random);
                }
                p = p.next;
            }
            //返回头结点，即原节点对应的value(新节点)
            return map.get(head);
        }
    }

    //复制一个加入原链表，再分离
    class Solution2 {
        public Node copyRandomList(Node head) {
            if(head==null) {
                return null;
            }
            Node p = head;
            //第一步，在每个原节点后面创建一个新节点
            //1->1'->2->2'->3->3'
            while(p!=null) {
                Node newNode = new Node(p.val);
                newNode.next = p.next;
                p.next = newNode;
                p = newNode.next;
            }
            p = head;
            //第二步，设置新节点的随机节点
            while(p!=null) {
                if(p.random!=null) {
                    p.next.random = p.random.next;
                }
                p = p.next.next;
            }
            Node dummy = new Node(-1);
            p = head;
            Node cur = dummy;
            //第三步，将两个链表分离
            while(p!=null) {
                cur.next = p.next;
                cur = cur.next;
                p.next = cur.next;
                p = p.next;
            }
            return dummy.next;
        }
    }

}
